947 717374
538477814 448651578 391840501 615537725 907496523 862788920 483612921 103308207 206519433 507672003 48672647 115656389 7455792 43430155 236946025 358741767 31182066 686641556 306766811 961181587 508436022 900986550 359813389 106595227 47123862 539810076 668101285 998748389 10105697 253134150 450009914 697875529 458698522 510952967 807110618 892598327 585182711 628830471 621954693 569344302 747150691 798351169 491289263 564238918 50541948 308621702 776555458 554285479 361838997 823459577 91748250 197057296 917637301 828896658 290174215 770562641 410298391 671372443 78753358 280474577 480598440 764361014 592284584 209718024 106360461 238897364 274200002 109213446 295505306 715627455 856771132 899580651 575263195 752426385 200588330 281555564 383558415 676820923 493987990 5144149 104581160 321775103 61345019 91516673 863270860 653474039 636275660 13173476 134664407 779451020 620639979 12634370 53683415 647753343 111865394 649724277 199778446 532042467 148768238 944125418 945029236 274787488 771413342 303626276 859336499 776856050 313774393 912145016 446119465 892422889 175825957 464409168 984946665 901491175 235097921 632063657 846340794 198147621 600616092 578946196 116416278 778598957 4157883 427436472 653532717 520803425 95472151 150730446 937536096 449039731 327227804 776013348 646663110 676741867 872460588 99826203 948156586 181071781 887473946 344228265 767706634 4628048 284582320 957013208 923337242 467456496 860081065 325261637 540931775 138517596 575331511 103592098 479483413 220217024 11294718 307877684 152326890 103552541 798319255 925067861 493132608 67485636 627903502 804792563 455255247 573537759 215109861 839163407 134621568 894066152 451918607 878389568 121816051 10310960 531436661 891648814 606352378 685027674 364673397 343505943 989712668 805578461 302539613 720151116 124336915 385814917 284661493 497952437 515230286 914933490 88062706 842146121 788646512 979783959 384312452 588117399 350223567 81247420 964413385 672913729 342994166 304729085 56534103 957572219 491817763 546597066 132028342 261290640 392873673 902432101 462073315 952587869 273389327 684049638 683096015 197203669 883031888 854221754 501602270 64555387 366863258 544603680 30958697 194943211 601024303 83088043 110746684 212388689 25378566 861455043 415670552 64976112 41831498 463428899 64863794 405668508 433592026 818154588 538592434 514373696 909499848 172546897 977540662 959459674 647462362 901049273 307220812 788140410 571470348 59139745 601911803 901081798 305602572 864794343 931770427 882586233 560802493 990810048 939784824 24188768 52041397 84013875 921429011 430393947 627851454 177533083 723814881 317802722 436391000 556118824 625843882 915602813 437492790 118909535 377039787 649899083 40229565 659034774 983350549 109670780 125748872 225749881 382554763 360266711 616784102 860445832 139578792 237712693 397595226 316981654 328544887 281263364 43668250 493470027 251145721 828103365 577477522 13538211 875116195 194367117 816663774 909232750 143209181 76974472 547995475 128947150 580305796 850309746 29256438 123997883 668286056 172468252 180204035 849318786 35413711 928581613 260403560 927535170 651397616 468754526 474523975 482765678 741455225 479916413 513457016 511018574 482924042 923041643 845768196 792111997 633637304 615284446 898429867 742927724 124881547 949191072 744162399 359186142 948373760 166378254 356566983 419720042 361808007 763135129 856959421 321774077 47519749 122408520 889830608 787564373 820074580 411984181 318128323 276202119 341444287 184354827 275193100 887849337 543662983 795499919 484379478 780636520 708362848 299616020 806181887 810368356 579161332 21564165 320548507 307801807 393118559 179554655 328117359 184848866 610809009 505592883 389160182 79192616 52462447 817761321 320371296 150764289 947362323 633642232 928624654 148619297 351518087 770173935 239984919 70437902 145983406 636884080 693693639 327449253 496802268 760242287 976377627 582721941 546304344 319453943 276106053 341978850 838114273 755618469 608890926 681632612 355088422 437979179 112096495 179555141 861668941 388087502 161130327 966220423 645018733 57228521 508380777 994031996 622433043 943671912 331729114 14178636 347959233 385223502 41260439 885061234 770840426 617767983 85022781 773916479 173826808 914202806 69019551 427735638 449297351 470736417 939046468 690759470 455585319 384068544 290408167 904601748 710816221 707389817 50364661 899182374 475192482 66248775 128900370 50550232 573663907 94851766 695417748 229607539 290592511 30448489 715502342 804685329 295691853 300391829 134034599 390562211 319986451 624101251 382972137 594019947 85281872 511469330 462595570 491437186 319633907 630204466 508729374 592770899 245921121 537806186 486796923 441990686 805941747 480699986 423146315 100386934 571550581 202700314 675868294 804524228 841897641 653939202 781813333 62980801 735403458 342748640 658728856 843631616 567329001 371565725 883486817 442881122 688309948 4426424 129001591 813471903 597015242 25853633 654661588 931024580 669717528 304041439 404238119 526066351 710435743 495010891 972620883 766269077 803988683 481651155 121546990 801534333 669126653 700664408 437770435 938470851 312478986 916453968 239311953 881776534 92516795 741892932 908877641 937152889 274793547 521269843 451504403 117452998 266492396 516820142 439579466 118018598 691595074 735244314 718477884 862414874 973722854 789207409 185583467 509868918 779699684 323014945 959258638 509748704 393841213 257345451 143590288 287551573 103865190 417888293 723430928 837688229 284872903 782135481 785780448 355954930 230748734 329422116 439908103 260283445 33882265 115638584 230354367 270406841 286505503 919343450 977222391 319519646 451705608 947714820 557601233 125272663 983269376 661538116 351239461 476562220 883789992 389985083 302469117 659594681 24163349 364505248 748209687 678018925 160955215 989503547 311615078 473746444 432498644 830793322 272427409 302034478 544232978 283538847 931404915 126238142 348427760 959987423 421603993 813110395 562402118 349983812 856165575 791638650 748332128 965653885 381932404 465892002 572786815 877285961 601653577 390074670 102033496 22398719 781423525 423585839 562491027 664023818 298806044 39484936 906984013 668770661 798828019 955455472 637684118 312410915 556717222 132192371 263379956 750976489 386340963 789497842 130301663 109318258 865736076 705864990 927672386 555220234 508540985 23538561 652552960 537635348 811778740 359833077 874977645 762384517 474210299 329453866 457359313 898447462 427527233 535070245 318229737 631237973 858559853 353045691 558631526 585646340 734968729 34891802 69353323 908587961 465801108 450092353 777591059 888186061 381943649 926758787 477466856 721932077 627124918 646038281 757471597 203263964 338553214 782694220 848625814 142821999 683550295 285557662 105892939 660042639 655242517 571037602 621630185 37469563 736582973 6664656 85945280 530455683 898596491 845507571 99233174 99791246 194065772 989479338 128867618 962689173 382650245 536767210 591678354 156132134 826271786 471666810 51876102 756163298 451744487 880376437 132259602 395856894 587868667 901268172 77437760 496079302 254457560 680265666 795675020 886408982 823782565 175082606 761716454 444543711 603026620 108990268 459801011 715757224 687336236 860608108 341564493 707643146 450912056 766098 685819262 381772339 469762005 892495636 604774153 388792932 732310064 489619631 114118689 644922995 394966054 856306675 418161136 750301770 41772235 186999746 506778642 293270886 691349220 522598357 112472343 6729049 110744940 955154743 539975428 950295112 407463443 202393288 650820050 175666541 166578618 43367867 767566830 445053334 601933560 307153944 646461112 848486820 991352472 427066171 829689604 820632333 669122585 445084755 850492828 112645211 656372781 601038564 975686075 648363947 761738042 176559429 56286099 549836079 200425948 952707363 760680648 787023788 764571489 855125500 756185332 117968125 539800139 18254245 804365857 638327950 100255954 807313093 509077842 268513249 1673567 922544471 899728122 999400205 887779090 87905580 156066690 832695610 483572798 792268903 986977736 948251430 218242791 152771071 125498267 736120739 291230027 179025472 77062208 883763734 351523926 837780810 684674288 472439034 182087212 634234769 304658263 798257243 130402979 744554075 722936855 503478364 692114886 157793861 871434563 108721073 753578067 945212863 556537060 187446821 132756542 155275147 850991480 354982678 785027884 385902914 943735405 340262900 412219641 220915151 743418539 579290310 241035826 903657969 902973191 240722084 229717660 180861629 880418001 560902718 839053227 128797211 946536007 199001171 484109580 364110660 811800863 639707707 291271451 63915850 111583489 785757790 447398253 662750608 782722571 376004283 113045320 720731726 157564236 534308706 875920934 478486798 821441865 253181178 594941494 588040498 386586234 235119932 679602395 283107948 932934606 658376053 618549547 983668035 688970531 478436616 586057841 127864213 5511631 579550698 59726507 276061455 187711770 285887781 302073612 840581047 554602689 770192213 174102139 543026787 679414133 980693294 108540947 760985407 464288090 852595188 655795105 137748043 396407432 115951617 253946409 953138651 76149134 205563714 640299618 784709909 199276522 861301178 815259445 212757622 196084370 802864127 699569217 735642702 243110510 194372024 866776154 151487295 539762395
662372901 946882566 879865538 428817961 208180375 642597375 960948642 808656926 66225395 67196340 249655422 696990322 109840947 324542919 770117195 282211153 400816869 898896016 980443344 443140060 730343850 971235992 508618025 499791016 673026488 783945503 272525381 191010877 290095961 465687192 104788840 349747096 127274602 771232551 566226602 300836521 733504733 482843434 49558389 446881494 416911671 345365421 325956362 773930358 819889426 523137268 934989053 674209879 92580252 986257141 346225589 943419961 255996951 548590555 950060781 901095249 310896727 257091717 653871158 653354439 241795399 480247556 125427059 858197560 291998052 309567264 459784539 181797428 3145536 639124180 765861882 766731457 300913664 758658254 801110832 627006166 744513503 470788848 618107184 306854881 635850409 339717330 794252035 677022786 732398656 279654973 81440515 693243853 694205211 924738481 628033888 461845580 227062978 107892448 388343454 298339323 568648275 715261233 553275925 557362186 970223360 721878590 852863600 948047135 404110479 334849110 327199791 468423633 119249881 583167228 457219621 935106350 487424331 881487717 7320058 54624566 201738600 793122558 867948713 32449885 877449028 197305317 910597379 509085453 495621387 125924203 52379179 41403938 241298552 904086168 528563225 154350956 820253022 319227559 796454423 464955184 127238179 374882181 712514374 544576936 844151872 780332118 90102042 83797886 849349826 277290481 849309146 606931541 625474252 731566943 886650657 72972608 636028435 651100767 789586528 525009737 298360160 349254629 695131993 54475756 268974866 314042007 833736869 113756057 623355801 173991759 350445616 525706805 388054012 856043932 460623800 904201625 460274772 965429824 638369617 87133202 767630415 495985587 14007779 755912927 39865262 319077535 228580266 822293175 615345863 235809378 845157558 459211328 324966659 404821903 416694633 834681497 652967777 140643437 388428540 760602577 775589106 740029814 366495225 949694829 289707867 610077145 103966914 512090342 883027286 676614649 459761673 562349097 435519281 831983596 915567958 930709013 645230413 450158589 243560325 820940032 225607840 486497579 125161797 16637747 173189427 135105960 439317914 605208425 75010725 385693018 4701275 919173460 976871079 548782173 659298484 993256472 463133054 971612542 493141926 644838094 93346437 54757570 176699010 960199939 438954664 210575325 712133490 512707894 172096233 665923772 602584560 862984541 446248670 865780732 250800461 614785376 536690993 51351920 981571883 225393053 664113183 64158 458126339 722653027 394799610 36475715 56166305 851889015 672152999 771275723 375757219 91036306 65981217 809916889 473757693 408015840 537702900 600828101 181231479 72576898 852343234 689211929 237570093 674360077 265477826 739607572 950420494 869688841 629122108 106480679 207203167 277666420 359353614 720972666 573035829 461934396 664284202 845277544 782241278 464345288 219136789 874158590 555559929 152015728 390758506 264362112 696579001 835058688 292239445 460114405 873561766 475626554 567208729 971134294 909321083 215760720 569056651 425966259 251647689 307855982 976972180 230271758 990223219 386201902 247065266 384084781 274017584 776708641 681969783 600791564 464887053 866612557 675748105 957793113 375770600 686272170 715486113 434761719 382995702 676381348 304665356 572136571 968806461 963073692 160714797 554296242 431704347 949388647 640716921 565671193 299605693 602479053 119028857 921785699 348258985 544600843 959780427 377836791 41450293 353022802 164170786 877574768 913906701 155407942 448888002 480270107 349148337 825786239 607959044 224331132 909256436 287125771 655175000 677349833 13328766 986538986 756996158 235505261 169704011 511248017 955421388 785104519 184172843 30185320 688170539 603171432 432699456 809341772 131526938 748560409 896721026 30903309 822740586 496659411 286219326 131986673 885357952 399467140 430711187 304872239 497799894 45247057 999444724 207697013 453002873 9994510 816652713 961204067 798342796 649532104 713445453 449716238 955167684 717808700 682885969 372498046 702266859 187987805 31955320 582276912 447578206 220636113 884873817 965319060 777162383 646837621 906748641 361153680 609112707 349656277 107574734 37298939 954555732 401278901 446131252 201134627 318080432 297914251 989710844 150017096 783137368 540891649 631434336 776714526 386994338 606356856 248484465 652491343 724918008 300330880 192210321 835270135 795125591 487512929 913096697 834727206 850654673 892354198 846177588 304084066 350537995 186888013 702417570 725042722 879316672 803664104 26845686 455021908 582788668 207084670 10649017 410824663 913414369 888274266 710414277 806314242 688301221 709909883 797003210 875963932 346768530 153185811 714655692 750925537 942745925 974552073 598246563 687486979 322418544 862418551 123282553 922967463 772715609 309316908 838121296 724350436 396848216 671301418 873409402 159083848 511786333 528832297 42978335 625322834 308253031 20558355 761945530 686325497 595721998 6121862 504903324 303801635 656276986 56496213 546664296 482933039 1104233 62263047 496706965 973548908 863385773 670469206 913292784 499279263 217235372 319189938 175402263 810260865 18590047 809447356 898507774 574809919 949979219 540010187 725994606 302471160 761296683 511664490 933058945 171513411 805829915 841831128 312741928 661962406 680359535 91545990 410073509 217406496 946652930 543635869 351434257 153140896 943790791 964043126 872854231 607820171 554561092 132557855 788579639 313534010 118697746 405425629 475053252 10179705 492640350 221849252 404501990 317474058 323540843 696976545 48542297 255221792 467405838 122471601 41371052 860055524 566217521 258671335 275825092 957330164 493906256 526183690 105794902 401857759 899079935 407304980 160988272 424886954 29877601 284537780 432270576 293731662 222683826 578119885 728077579 674152503 482573503 772889589 943333320 248847302 746303337 852618999 980340099 897400273 377851686 986864721 876025451 455623710 891819904 281803703 237507331 119604459 558268308 90851470 101790884 554984809 62098067 292231282 267511802 943052348 978776644 497291696 303122819 576111613 943232896 597854156 613616148 564914616 15427253 799212029 70665555 468718958 169453668 456693676 375804477 312439956 221161380 730283257 343322530 498364563 576864412 856216886 466856612 219457350 177128204 42809193 753740604 27720575 728962757 416142030 18932917 338081665 222368300 992820563 265839663 186536839 403522747 481074715 336242461 820912700 151991680 61465596 185008583 419024706 583077789 879544833 981905865 75633579 753790150 326487528 199390354 903415427 173678022 362072740 371722726 16754500 589736186 81348316 620862045 813727327 96318676 157177195 903414754 274709946 289435737 156458974 694746676 686349613 999195556 930326265 807272808 188491524 733986401 810942258 342682213 656619648 757335122 964064052 17645414 571298390 732595150 314637918 11865212 536315182 938465341 228772674 681731594 625539109 882913437 770327078 796530503 701827403 827690496 892054918 729870527 993654310 715143180 625498256 825458898 587698734 850298745 703875494 687499316 93023055 180266647 611919584 413111915 425947242 783070149 781345415 504290901 925392339 445380091 80590747 468629151 896319444 517211457 787702350 445963342 666367273 329744182 962364039 530126138 212795267 390258570 377059425 223793806 226907653 308379779 361240233 670875466 394952650 18510716 225455971 855938753 275869277 778066786 595776069 943676187 847868991 576540982 670763834 152408532 477737828 554482829 895060192 799520315 635528630 476703763 651646219 133678068 660270993 425768963 720462656 352956791 561756741 345826481 775315770 116000911 794851480 640880896 149192041 408998107 792843073 284794092 190113134 66601040 576569198 515357698 10073761 484327349 772237631 785794531 865469067 557418789 174411336 446831813 269342060 544843921 768872979 975371761 1698486 232472636 615259804 623566406 406567311 848342333 75842771 168458421 402654036 393785856 310935325 200092867 665094673 516452549 364291028 331357450 57344777 247912992 819579842 845420472 697731892 566030711 562686634 40210702 503844284 140855175 994778048 843437538 244141183 222341856 816313899 604339229 933538960 13368932 836374410 447893310 852966070 83048908 940568172 750579926 320717804 729819171 125590230 112390410 20306911 348845641 293169858 243923220 51948403 319774065 880886426 879561154 340598079 52498851 203500481 56328694 437881868 851501627 50420490 442909988 644372825 705220200 133952319 598490583 888061914 994290606 527251355 35334188 376418805 2571876 337581136 954267732 551639619 193076279 389140227 580364567 73093141 263742629 871517003 403860044 658668013 687025027 355091253 667191138 518012416 86998392 809018819 47678427 626087611 856873087 626208616 41937867 942861627 450433641 516003469 252394589 376972243 635242329 299184144 55396430 54113930 937885254 86488000 863053424 6786970 342098812 91231970 427677225 253911539 149190939 674120879 895821809 677268405 636781463 841675987 304188888 106147002 749595702 996854256 665800701 846340362 563421077 538044441 949228824 56256868 580239396 151103831 736368369 875313084 542083237 783232040 914522342 453373367 315273905 772058619 569434729 556832560 57046323 134290357 85613440 486218423 474394858 208563247 414055748 496642573 627932395 498498741 951151714 876796586 155213086
